from docHelpers_ipython import Doc, romania_location_map_open
from IPython.display import display, Image
doc = Doc(romania_location_map_open)
mappy = doc.showMap(['A','B'])
display(Image(mappy))
Since this is a very simple problem, we already know the route at just looking at it. Its via S and F like shown below. We will check our algorithm will arrive at that solution.
mappy = doc.showMap(['A','S','F','B'])
display(Image(mappy))
The very crux:¶
Imagine we are at Arad (or node 'A').
Are we arleady at goal? No 'A' is not the goal. We need to make a move.
We have 3 options to choose from for our next move. S, T, Z. Why? Because those are the only cities/nodes connected to A. We will choose one. Say, we chose 'S'. After our first move, we will have again two choices 'RV', 'F'. And so on from first step.
This is the first basic foundational intuition of developing our algorithm
Strategy, Strategy, Strategy:
In 2nd step above, we have to choose among ['S','T','Z']. How do we decide. We need a strategy. Basically a variety of decision making here, spawns into different algorithms. Imagine we put letters ['S','T','Z'] in a bag. And that bag has a peculiar characteristic.
Define our bag:
The peculiar characteristic is that, you cannot pick up at random any letter from the bag. What went first, comes out first. First In First Out, FIFO. For example, in empty bag, if you had first put 'S', followed by 'T', followed by 'Z', then when you pick up one, it would be 'S'. Let us say, taking the letter from the bag is called popping.
ITERATION 1
We could now try to derive a series of steps as below.
1. Put 'A' in our bag. 2. Pop the bag, so 'A' falls out. (yeah, sounds stupid, but this is just to establish pattern as we see shortly) 3. Is 'A' our goal? Nay. 4. Take neighbors of 'A'. Put them in the bag alphabetically. (So 'S' goes in first, then 'T', then 'Z').
In 4th step, you could choose any strategy for adding to queue. Alphabetically, reverse alphabetically, random, etc. This is an additional strategy, but we just keep it simple (alphabetically) and its already stored that way in our graph dictionary.
We already have 'bag' implemented in python. We could simply use deque class object. Let us try to implement above steps. Note we also will 'construct' visually a tree and a stack like diagram alongside, for better visualization.
from collections import deque
M = romania_location_map_open
start = 'A'
goal = 'B'
bag = deque()
bag.append(start) # put 'A' in our bag
current_node = bag.popleft() # Pop the bag, so 'A' falls out. popleft is for FIFO
if current_node is not goal: # Is 'A' our goal? Nay.
for each_neighbor in M.get(current_node,[]).get('connections',[]): # Take neighbors of 'A'
bag.append(each_neighbor) # Put them in the bag alphabetically (already sorted in M so no need to do here)
list(bag) #print the current contents of bag
#visualizing..
from IPython.core.display import HTML
doc = Doc(romania_location_map_open)
resultHTML = doc.computeGraphs('A',['S','T','Z'], mappy=True, tree=True, queue=True, HTML=True)
HTML(resultHTML)
Let us repeat what we just did again!
ITERATION 2
We do this only if bag is not empty. If bag empty, it would mean, there is no more cities to search and we failed.
1. Is bag empty? No, we put ['S', 'T', 'Z'] in just last step. So proceed. 2. Pop the bag. 'S' falls out. (as that went in first, last time) 3. Is 'S' our goal? Nay. 4. Take neighbors of 'S' which are 'F', 'RV'. Put them in the bag alphabetically. (Note bag already has 'T','Z' from last time)
Coding it..
if bag: # Is bag empty? No, we put ['S', 'T', 'Z'] in just last step. So proceed.
current_node = bag.popleft() # Pop the bag. 'S' falls out.
if current_node is not goal: # Is 'S' our goal? Nay.
for each_neighbor in M.get(current_node,[]).get('connections',[]): # Take neighbors of 'A'
bag.append(each_neighbor) # Put them in the bag alphabetically (already sorted in M so no need to do here)
list(bag) #print the current contents of bag
Visualizing it..
resultHTML = doc.computeGraphs('S',['F','RV'], mappy=True, tree=True, queue=True, HTML=True)
HTML(resultHTML)
We have traversed now till 'S'. One might guess we are just one node away from 'B', but alas, in our 'strategy', we have other nodes in front. Note 'T' which would be our next candidate, but hey hold that thought. Our next algorithm caters does better job in traversing forward like you just imagined. One more iteration..
ITERATION 3
1. Is bag empty? No. 2. Pop the bag. 'T' falls out. 3. Is 'T' our goal? Nay. 4. Take neighbors of 'T' which is just 'LU'. Put it in the bag.
Coding it..
if bag:
current_node = bag.popleft()
if current_node is not goal:
for each_neighbor in M.get(current_node,[]).get('connections',[]):
bag.append(each_neighbor)
print(list(bag))
resultHTML = doc.computeGraphs('T',['LU'], mappy=True, tree=True, queue=True, HTML=True)
HTML(resultHTML)
Yes, as you guessed, next would be 'Z' and it would take another 6 iterations to arrive at goal this way. But you already can see, the code crux is repeating, and we are traversing each node, every time we pop off the bag. Below is our code crux, which now we could wrap in a loop now and check.
if bag:
current_node = bag.popleft()
if current_node is not goal:
for each_neighbor in M.get(current_node,[]).get('connections',[]):
bag.append(each_neighbor)
Earlier we said, once bag is empty, we are done. That shall be our exit strategy for our loop. It would be something like below. Replace 'if' with 'while'.
while bag: #we do this as long as bag has something
current_node = bag.popleft()
if current_node is not goal:
for each_neighbor in M.get(current_node,[]).get('connections',[]):
bag.append(each_neighbor)
For remaining nodes, we shall just check the code in loop and see how it goes. Note, bag would be empty only after all nodes are traversed. But that is not our aim. In one of upcoming iterations, we would find 'B' for sure. At that time, we just exit (and that is our successful exit). Integrating successful exit..
while bag: #eventual failure exit
current_node = bag.popleft()
if current_node is goal: # successful exit
print('Success. Goal found. Current node: ',current_node)
break
for each_neighbor in M.get(current_node,[]).get('connections',[]):
bag.append(each_neighbor)
Checking it..
while bag: #eventual failure exit
current_node = bag.popleft()
if current_node is goal: # successful exit
print('Success. Goal found. Current node: ',current_node)
break
for each_neighbor in M.get(current_node,[]).get('connections',[]):
bag.append(each_neighbor)
print(list(bag))
Whew. Great. We have done it. Found the goal!!
But wait. What is the actual problem statement? We need to find a route! We just exited once we found the goal node.
Before we get in to that, let us wrap it up once again in a full function as below reinitializing and repeating the same loop. Let us also print bag contents in each iteration. Recalling from ITERATION 1, till current step..
(Hold on for Visualization)
from collections import deque
M = romania_location_map_open
start = 'A'
goal = 'B'
bag = deque()
bag.append(start)
while bag: #eventual failure exit
current_node = bag.popleft() # FIFO
if current_node is goal: # successful exit
print('Success. Goal found. Current node: ',current_node)
break
for each_neighbor in M.get(current_node,[]).get('connections',[]): # add neighbors
bag.append(each_neighbor)
print(list(bag)) # to show bag contents during each iteration
print(list(bag))
How do we now track path? Imagine, if during every iteration, we recorded parent of each node traversed (parent is the node from which we could arrive at current node), then we could use that dictionary, to create a path backwards to start (and then reverse it while presenting as solution).
In our main loop, the optimal place is when we traverse each neighbor to add to the bag! Each neighbor is automatically child of current_node, in other words, current_node is parent of each neighbor we traverse.
We will simply create a cameFrom dict, record the parents as we just discussed, and analyze how we could use that information to create a path. Note parent of 'A' would be None caz its our starting node.
from collections import deque
M = romania_location_map_open
start = 'A'
goal = 'B'
bag = deque()
bag.append(start)
cameFrom = { 'A':None } # dictionary caz child:parent pair (key:value)
while bag: #eventual failure exit
current_node = bag.popleft() # FIFO
if current_node is goal: # successful exit
print('Success. Goal found. Current node: ',current_node)
break
for each_neighbor in M.get(current_node,[]).get('connections',[]): # add neighbors
bag.append(each_neighbor)
cameFrom[each_neighbor] = current_node #current node parent of its neighbors(?!)
print(list(bag))
print(cameFrom)
Now we need to traverse backwards. From above cameFrom result, you could manually trace back path as below.
Now current_node is 'B'
- Let Path = [current_node] , that is
['B'] - Current_node is 'B'. Its parent from cameFrom is 'F'. Make Current_node = 'F' now. Append to Path =
['B','F']. - Current_node is 'F'. Its parent from cameFrom is 'S'. Make Current_node = 'S' now. Append to Path =
['B','F','S']. - Current_node is 'S'. Its parent from cameFrom is 'A'. Make Current_node = 'A' now. Append to Path =
['B','F','S','A']. .
We could exit, since 'A' is start. If our function is not given start node, we could also exit next as below
- Current_node is 'A'. Its parent from cameFrom is None. Make Current_node = None now. Append to Path =
['B','F','S','A',None].
Since Current_node is None. We could stop, strip Path list (remove None), and return.
Let us check this programmatically manually.
Path = [current_node]
print(Path)
current_node = cameFrom[current_node] # Now current node would become 'F'
Path.append(current_node)
print(Path)
current_node = cameFrom[current_node] # Now current node would become 'S'
Path.append(current_node)
print(Path)
current_node = cameFrom[current_node] # Now current node would become 'A'
Path.append(current_node)
print(Path)
current_node = cameFrom[current_node] # Now current node would become 'None'
Path.append(current_node)
print(Path)
Great. We are now able to construct path from cameFrom. We could just wrap above steps in a loop (exit when current_node is None), and return trimmed path.
current_node = 'B' #just to redo again, but now in loop
Path = [current_node]
while current_node is not None:
current_node = cameFrom[current_node] # Now current node would become 'A'
Path.append(current_node)
print(Path[:-1]) # trimming
Now that we could also get the path, let us wrap it all in functions, modularize and check once again. We will also rename bag to openSet, as that is more conventional (sigh!!), can be relatable to many pseudocodes seen for such search algorithms.. Also note, how we have reversed the path calculated.
from collections import deque
cameFrom = { } # This has to be globally accessible for reconstructPath to
def reconstructPath(current_node):
Path = [current_node]
while current_node is not None:
current_node = cameFrom[current_node] # Now current node would become 'A'
Path.append(current_node)
return reversed(Path[:-1]) # trimming
def ourSearchAlgo(start, goal): # Wait, we havent named yet?
# INITIALIZATION
openSet = deque()
openSet.append(start)
cameFrom[start] = None
# MAIN LOOP
while openSet: #eventual failure exit
current_node = openSet.popleft() # FIFO
if current_node is goal: # successful exit
print('Success. Route from {} to {} found. Path: {}'.format(start,goal,list(reconstructPath(current_node))))
break
for each_neighbor in M.get(current_node,[]).get('connections',[]): # add neighbors
openSet.append(each_neighbor)
cameFrom[each_neighbor] = current_node
return 'No Goal found!'
M = romania_location_map_open
start = 'A'
goal = 'B'
result = ourSearchAlgo(start, goal)
Voila! Our Search Algorith successfully worked. Let us try few more options. What about goal 'M'?
start = 'A'
goal = 'D'
result = ourSearchAlgo(start, goal)
One more..
start = 'A'
goal = 'N'
result = ourSearchAlgo(start, goal)
Whew. Great, our algorithm seems to be working fine. :)
Visualization (Optional)¶
We will inject a small code to keep track of bag contents, nodes traversed for sake of visualization. And then render an animation to visualize how nodes were traversed to reach the goal.
from collections import deque
from docHelpers_ipython import Doc, romania_location_map_open #Doc for visualization
# VISUALIZATION PURPOSE
from IPython.display import display, Image
cameFrom = { } # This has to be globally accessible for reconstructPath to
def reconstructPath(current_node):
Path = [current_node]
while current_node is not None:
current_node = cameFrom[current_node] # Now current node would become 'A'
Path.append(current_node)
return reversed(Path[:-1]) # trimming
def ourSearchAlgo(start, goal): # Wait, we havent named yet?
# INITIALIZATION
openSet = deque()
openSet.append(start)
cameFrom[start] = None
# MAIN LOOP
while openSet: #eventual failure exit
current_node = openSet.popleft() # FIFO
if current_node is goal: # successful exit
print('Success. Route from {} to {} found. Path: {}'.format(start,goal,list(reconstructPath(current_node))))
break
for each_neighbor in M.get(current_node,[]).get('connections',[]): # add neighbors
openSet.append(each_neighbor)
cameFrom[each_neighbor] = current_node
# VISUALIZATION PURPOSE
_ = doc.computeGraphs(current_node, M.get(current_node,[]).get('connections',[]))
# VISUALIZATION PURPOSE
_ = doc.computeGraphs(current_node, M.get(current_node,[]).get('connections',[]))
return 'No Goal found!'
M = romania_location_map_open
start = 'A'
goal = 'B'
# VISUALIZATION PURPOSE
doc = Doc(M)
result = ourSearchAlgo(start, goal)
# VISUALIZATION PURPOSE
display(Image(doc.render()[0]),Image(doc.render()[1]),Image(doc.render()[2]))
Observe the nature of traversal. Especially tree/map gif, one could observe, we are going 'layer' by 'layer'. This is thus a Breadth First Search (BFS). We finish checking all neighbors, and then go behind all neighbors of each of those neighbors and so on.
We have successfully derived a BFS algorithm for a tree problem. :)